package com.leetcode.剑指offer专项突击版;

/**
 * @author 覃国强
 * @date 2022-02-28 20:35
 */
public class 剑指OfferII_009_乘积小于K的子数组 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] nums = {10,5,2,6};
    int k = 100;
    int answer = solution.numSubarrayProductLessThanK(nums, k);
    System.out.println(answer);
  }

  static
  class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
      if (nums == null || nums.length == 0 || k == 0) {
        return 0;
      }

      int left = 0;
      int right = 0;
      int product = 1;
      int answer = 0;

      while (left < nums.length) {
        // 找到第一个不满足的右边界
        while (right < nums.length && product * nums[right] < k) {
          product *= nums[right];
          ++right;
        }

        if (left < right) {
          // 存在包含 num[left] 的子数组, 计算必须包含 num[left] 的子数组个数
          answer += right - left;
          product /= nums[left];
          ++left;
        } else {
          // 不存在包含 num[left] 的子数组
          ++left;
          ++right;
        }
      }

      return answer;
    }
  }

}
